package primary.primary0;

import java.util.Arrays;

/**
 * 双指针
 */
public class S0075颜色分类 {

    /**
     * 100， 10， 双指针
     * 答案里看的，
     * 挺有意思，三个指针，0指针和2指针分别在首位，指向可以换的位置，0指针之前全是0,2指针之后全是2
     * 然后aimLoc从前到后移动，遇到0的话和换一下，遇到2和2换一下，注意换完之后的移动策略，是0,1,2三种case的话，还是不一样的。要画个图看下
     */
    public void sortColors3(int[] nums) {
        int totalLen = nums.length;
        int zeroLoc = 0;
        int twoLoc = totalLen - 1;

        int aimLoc = 0;
        // 注意这个 <= 的 = ，非常重要，交界处的判断要异常小心
        while(aimLoc <= twoLoc){
            // 因为我指针是从前往后走的，所以 == 0和 == 2的决策并不一样
            if(nums[aimLoc] == 0){
                swap(nums, zeroLoc, aimLoc);
                zeroLoc ++;
                aimLoc ++;
            } else if (nums[aimLoc] == 1) {
                aimLoc++;
            }else {
                swap(nums, twoLoc, aimLoc);
                twoLoc --;
            }
        }
    }

    private static void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }



    /**
     * 100， 33
     * 只能原地排序，先数出来0 1 2数量，然后从前到后写入
     * 这里看了下评论区，有个用数组的方式挺不错，可以适配很多种输入，不只是0 1 2三种，更多的也行
     */
    public void sortColors2(int[] nums) {
        int totalLen = nums.length;
        int[] counts = new int[3];

        for(int num : nums){
            counts[num]++;
        }
        int alterLoc = 0;
        for(int i = 0; i < counts.length; i++){
            while(counts[i]-- > 0){
                nums[alterLoc++] = i;
            }
        }

    }


    /**
     * 3， 39
     * 从前到后，每找到一个蓝色的，就从后面找一个不是蓝色的，和他交换
     * 然后就得到一个 前面是红白交叉，后面是蓝色的，从前到后，看到一个白色的，就找一个红色的去交换
     */
    public void sortColors(int[] nums) {
        int totalLen = nums.length;

        int swapLoc = totalLen - 1;

        for(int i = 0; i < swapLoc; i++){
            if(nums[i] == 2){
                while(swapLoc > i){
                    if(nums[swapLoc] != 2){
                        // 交换
                        int temp = nums[i];
                        nums[i] = nums[swapLoc];
                        nums[swapLoc] = temp;
                        swapLoc --;
                        break;
                    }
                    swapLoc --;
                }
            }
        }
        System.out.println(Arrays.toString(nums));
        System.out.println(swapLoc);

        for(int i = 0; i < swapLoc; i++){
            if(nums[i] == 1){
                while(swapLoc > i){
                    if(nums[swapLoc] == 0){
                        // 交换
                        int temp = nums[i];
                        nums[i] = nums[swapLoc];
                        nums[swapLoc] = temp;
                        swapLoc --;
                        break;
                    }
                    swapLoc --;
                }
            }
        }
    }


    /**
     * 3， 37
     * 比上面这个更合适的一种交换方式，从前到后，这样不用考虑被交换的位置和交换的位置一样的情况
     */
    public void sortColors0(int[] nums) {
        int totalLen = nums.length;

        int swapLoc = 0;

        for(int i = 0; i < totalLen; i++){
            if(nums[i] == 0){
                // 交换
                int temp = nums[i];
                nums[i] = nums[swapLoc];
                nums[swapLoc] = temp;
                swapLoc ++;
            }
        }
        System.out.println(Arrays.toString(nums));
        System.out.println(swapLoc);

        for(int i = swapLoc; i < totalLen; i++) {
            if (nums[i] == 1) {
                // 交换
                int temp = nums[i];
                nums[i] = nums[swapLoc];
                nums[swapLoc] = temp;
                swapLoc++;
            }
        }
    }
}
